package com.cat.binaryTree;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/complete-binary-tree-inserter/
 * @create 2025/9/29 19:31
 * @since JDK17
 */

public class CBTInserter {
    TreeNode root;
    Deque<TreeNode> q = new ArrayDeque<>();
    public CBTInserter(TreeNode root) {
        this.root = root;
        q.add(root);
    }

    public int insert(int val) {
        while (!q.isEmpty()) {
            var node = q.poll();
            if (node.left == null || node.right == null) {    // 左节点为null
                if (node.left == null) {
                    node.left = new TreeNode(val);
                } else {
                    node.right = new TreeNode(val);
                }
                q.addFirst(node);
                return node.val;
            }
            q.add(node.left);
            q.add(node.right);
        }
        return -1;
    }

    public TreeNode get_root() {
        return root;
    }
}
